package cc.willrock.algorithm.sort;

import java.util.Arrays;

public class InsertSort {
	//最好O(n)
	//平均O(n×n)
	//最坏O(n×n)
	public static  int [] sort(int [] dest){
		for(int i =1;i<dest.length;i++){
			//insert
			int j= i-1;
			int value = dest[i];
			while(j>=0 && dest[j]>value){
				dest[j+1] = dest[j];
				j = j-1;				           
			}
			dest[j+1] = value;
			System.out.println(Arrays.toString(dest));
		}	
		return dest;  
	}	

	
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int a[]  = {15,9,8,1,4,11,7,12,13,6,5,3,16,2,10,14};
		System.out.println(Arrays.toString(a));
		System.out.println(Arrays.toString(sort(a)));
	}
}
